package pers.sloera.leetcode.editor.cn;

/**
 * 礼物的最大价值
 *
 * @author sloera
 * @date 2023-03-08 23:03:26
 */
class LiWuDeZuiDaJieZhiLcof {
    public static void main(String[] args) {
        Solution solution = new LiWuDeZuiDaJieZhiLcof().new Solution();
        System.out.println(solution.maxValue(new int[][]{{1, 3, 1}, {1, 5, 1}, {4, 2, 1}}));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int maxValue(int[][] grid) {
            int[][] dp = new int[grid.length][grid[0].length];
            for (int i = 0; i < grid.length; i++) {
                for (int j = 0; j < grid[i].length; j++) {
                    int maxLeft = 0;
                    int maxUp = 0;
                    // 第0行没有上一行
                    if (i > 0) {
                        maxUp = dp[i - 1][j];
                    }
                    // 第0列没有上一列
                    if (j > 0) {
                        maxLeft = dp[i][j - 1];
                    }
                    // 当前位置的最大值 = 上一个位置的最大值（左或上）+ 当前位置的值
                    dp[i][j] = Math.max(maxLeft, maxUp) + grid[i][j];
                }
            }
            return dp[grid.length - 1][grid[0].length - 1];
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}
